package double_pointer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-12-03
 * Time: 16:31
 */
public class ReorderList {
    public static void reorderList(ListNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        ListNode midNode = midNode(head);
        ListNode list1 = head;
        ListNode list2 = midNode.next;
        midNode.next = null;
        list2 = reverseList(list2);
        mergeLists(list1, list2);
    }

    private static void mergeLists(ListNode list1, ListNode list2) {
        ListNode l1_next;
        ListNode l2_next;
        while (list1 != null && list2 != null) {
            l1_next = list1.next;
            l2_next = list2.next;

            list1.next = list2;
            list1 = l1_next;

            list2.next = list1;
            list2 = l2_next;
        }
    }

    private static ListNode reverseList(ListNode list2) {
        ListNode prev = null;
        ListNode cur = list2;
        while (cur != null) {
            ListNode nextNode = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextNode;
        }
        return prev;
    }

    private static ListNode midNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = null;
        reorderList(listNode);
    }
}
